package org.example.game.history;

import java.util.ArrayList;
import java.util.List;

/**
 * @Description: TODO
 * @Author wyatt
 * @Data 2024/07/21 11:06
 */
public class Solution100329 {

    public static void main(String[] args) {
        System.out.println(new Solution100329().minimumOperations(new int[]{9,2,6,10,4,8,3,4,2,3}, new int[]{9,5,5,1,7,9,8,7,6,5}));
    }

    public long minimumOperations(int[] nums, int[] target) {
        int[] diff = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            diff[i] = nums[i] - target[i];
        }
        long count = 0;
        List<List<Integer>> list = new ArrayList<>();
        boolean flag = diff[0] > 0;
        List<Integer> subList = new ArrayList<>();
        list.add(subList);
        for (int i = 0; i < diff.length; i++) {
            if(diff[i] == 0){
                List<Integer> emptyList = new ArrayList<>();
                list.add(emptyList);
                continue;
            }
            int value = Math.abs(diff[i]);
            if(flag == (diff[i] > 0)){
                list.get(list.size()-1).add(value);
            }else {
                List<Integer> nextList = new ArrayList<>();
                nextList.add(value);
                list.add(nextList);
            }
            flag = diff[i] > 0;
        }

        count += calList(list);
        return count;
    }

    private long calList(List<List<Integer>> list) {
        long count = 0;
        for (List<Integer> values : list) {
            count += calSubList(values);
        }
        return count;
    }

    private long calSubList(List<Integer> values) {
        long count = 0;
        if(values.size() == 0){
            return 0;
        }
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < values.size(); i++) {
            min = Math.min(min, values.get(i));
        }

        count = min;
        List<Integer> newSubList = new ArrayList<>();
        for (int i = 0; i < values.size(); i++) {
            int value = values.get(i) - min;
            if(value > 0){
                newSubList.add(value);
            }else {
                count += calSubList(newSubList);
                newSubList = new ArrayList<>();
            }
        }
        count += calSubList(newSubList);
        return count;
    }


}
